Giữa những năm 1959 và 1962, nhiều cuộc đàm phán được tiến hành giữa các bên Đế quốc Anh, Malaya, Singapore, Sabah và Sarawak nhằm tiến tới thành lập một nhà nước liên bang mới - Liên bang Malaysia. Tuy vậy, Philippines và, đặc biệt là, Indonesia đã phản ứng dữ dội về sự có mặt của Sarawak và Sabah trong chính thể liên bang đang được thành hình này. Ngay trên phần bắc đảo Borneo, sự phản đối dữ dội cũng tới từ nhiều cánh chính trị: một số cánh chính trị địa phương từ lâu đã trù định nhằm thành lập một nhà nước độc lập cho riêng họ trên phần bắc bán đảo Borneo. Ngay như Charles Vyner Brooke, ông vua cuối cùng người da trắng của Sarawak, cũng từng có dự định như vậy, nhưng đã từ bỏ ý định đó từ năm 1941.

Từ thập niên 1950, những nhóm cánh tả và nhóm cộng sản, vốn hoạt động sôi nổi và mạnh mẽ trong cộng đồng người Hoa tại Sarawak, đã tuyên truyền mạnh mẽ cho sự ra đời của một nhà nước cánh tả tên là Bắc Kalimantan. Ý tưởng về nhà nước này, thoạt kì thủy, được khởi xướng bởi A.M. Azahari, nhà lãnh đạo của Đảng Nhân dân Brunei từ thập niên 1940. Ý tưởng này đương nhiên là đối chọi và là cản lực chính yếu với những hoạt động đang được tiến hành để thành lập nhà nước Liên bang Malaysia. Azahari, Yassin Affandi và những cộng sự lập luận rằng những khác biệt và xung khắc trên mọi mặt kinh tế, lịch sử, chính trị, văn hóa giữa Borneo và phần bán đảo Malaysia khiến cho ý tưởng về một nhà nước bao trùm trên cả bán đảo Malaysia và Borneo là không hiện thực.

Ngược với cách nghĩ của phần đông mọi người, căn cứ vào tài liệu và tư liệu lịch sử thì cho tới nay chưa có bất cứ một bằng chứng xác đáng nào chứng tỏ rằng Tổng thống Indonesia thời kì này, ông Sukarno có tham vọng về lãnh thổ trên đất Sarawak. Sukarno đã tuyên bố mạnh mẽ từ năm 1945 rằng Indonesia chỉ cố gắng giành lại và ấn định biên giới quốc gia trên những phần đất đã từng là thuộc địa của Hà Lan trước đây mà thôi. Có thể chứng thực khá rõ quan điểm này của Sukarno bằng những hành động thực tế khi Sukarto, trong khi luôn nhấn mạnh và nỗ lực giành quyền kiểm soát phần đất Tây Papua, thì dường như không hề có một hành động nào chứng tỏ muốn sáp nhập và kiểm soát Đông Timo - vốn là thuộc địa của Bồ Đào Nha.

Tuy vậy, chính phủ của Sukarno đã can thiệp bằng nhiều cách vào tình hình Bắc Borneo trong thời gian này. Với lo sợ sự kiểm soát của nhà nước Malaysia trên phần Bắc Borneo sẽ ảnh hưởng trực tiếp và mạnh mẽ tới quyền lợi của mình, Sukarno đã tiếp sức cho nhiều lực lượng chống đối Malaysia. Từ trước khi có chiến tranh với Malaysia, nhiều đoàn gián điệp Indonesia đã được gởi tới hoạt động tại vùng này.